package 校招笔试.美团笔试.美311;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/12 18:13
 */
public class 美团最大收益 {

    /*
     2.  （移步  **美团的最大收益** ）
      这个题，递归的顺序进行一个新的 思考！
      不仅要会正序， 也要回倒序！
      这个 没法倒序吗 ?  根据这个题的逻辑 好像是没法 倒序的，
      所以 正序的 方式也要掌握！

      ==
      这个题还是有些 复杂的说实话! (不能倒序吗? 整的不能 倒序 递归吗 ?)
      之后 把 记忆化 搜索写一下, 在一下 dp
      ==
      而且 这个题,还是一个 另类的 dp
      ,还需要 再 遍历 一下缓存表, 才能, 找出最优值
      dp[n][m] 并不是 最优值, 需要遍历,二维表 去寻找 最优值!
     */


    public int solution() {

        return 0;
    }

    /*
      注意下： 这种方式
     */

    public int recursion(int i, int j, int k, int colors[][], int reward[][]) {
        if (i == 0 && j == 0) {
            return 0;
        }
        int ansI = -1, ansJ = -1;
        /*
         注意 这种判断逻辑， 有点小妙！ 等下体会一下！

        ==根据题意
        f(i,j) 只可能 由 f(i - 1,j) or 或者 f(i,j - 1) 到达.
        但是如果 f(i - 1,j) or 或者 f(i, j - 1) 本身 就不可达 (不可达 值为 -1), 那就没办法向下进行了!
        (如果不判断这一点的 会有 问题!)
         */
        int tempI = recursion(i - 1, j, k, colors, reward); // 上一次的 状态的  财产（最大收益）
        if (i > 0 && tempI != -1) { // i > 0 保证数组不越界, 而 tempI 保证,只有在上一个节点,可达的情况下, 当前节点 才有可能 可达!
            //
            if (colors[i - 1][j] == colors[i][j]) {
                ansI = tempI + reward[i][j];
            } else if (tempI - k >= 0) { // 判断， 当前 支付 k ， 会不会欠费（ < 0） // 欠费, 则结束了
                ansI = tempI - k + reward[i][j];
            }
            // 如果 不满足上面, 则说明,f(i , j) 不能 由 f(i - 1,j) 达到
        }
        int tempJ = recursion(i, j - 1, k, colors, reward);
        if (j > 0 && tempJ >= 0) {
            if (colors[i][j - 1] == colors[i][j]) {
                ansJ = tempJ + reward[i][j];
            } else if (tempJ - k >= 0) {
                ansJ = tempJ + reward[i][j];
            }
            //如果 不满足 上面, 则说明, f(i ,j ) 无法 由f(i, j - 1) 达到
        }
        // ansI 和 ansJ 都是  -1 则说明 当前点, 不可达
        return Math.max(ansI, ansJ);
    }


    /*
     2023/5/26
     明显的 ： 起点 确定，  终点，根本就不确定的问题
     很明显的终点不确定， 只能够正序了
     */

    public int function(int[][] colors, int money[][], int k) {
        int n = colors.length;
        int m = colors[0].length;

        return process(n - 1,m - 1, colors,money,k);
    }

    /*
      f(i, j) 表示的含义是： 从 起点（0，0） 开始出发， 到达 f（i，j） 能够获得的最大 收益 （i，j）（正序）
      f（i，j） 表示的是： 从（i，j） 到达 终点 的最大收益 ， 问题终点 在 哪个位置呢？ ， 你去描述一下 这个过程，你会发现， 有点抽象的，根本没法进行

     */
    public int process(int i, int j, int colors[][], int money[][], int k) {
        // 越界
        if (i < 0 || j < 0) {
            return 0;
        }
        int ans1 = 0, ans2 = 0;
        // (i - 1,j)   这里要确保 i - 1 不能越界
        if (i - 1 >= 0 && colors[i - 1][j] == colors[i][j]) {
            ans1 = process(i - 1, j, colors, money, k) + money[i][j];
        } else if (i - 1 >= 0 && colors[i - 1][j] != colors[i][j]) {
            int temp = process(i - 1, j, colors, money, k) - k;
            ans1 = temp >= 0 ? temp + money[i][j] : 0;
        }

        // (i, j - 1) 一旦涉及到 i - 1 或者 j - 1 or x - 1， 一定要思考下，此处有没有可能会出现越界的情况！
        if (j - 1 >= 0 && colors[i][j - 1] == colors[i][j]) {
            ans2 = process(i, j - 1, colors, money, k) + money[i][j];
        } else if (i - 1 >= 0 && colors[i][j - 1] != colors[i][j]) {
            int temp = process(i, j - 1, colors, money, k) - k;
            ans2 = temp >= 0 ? temp + money[i][j] : 0;
        }
        return Math.max(ans1, ans2);
    }

    /*
    上述的代码， 是有问题的 ， 就是 在判断 两个 格子的 color 相同的时候， 没有思考一个点：
    前一个节点 可不可 达， 如果 pre 节点 都 到不了的话， 那么 即使 pre -> cur 花费0 ,那么 pre -> cur 这条路线也是不可达的!
     */
    public int processUpdate(int i,int j,int colors[][],int money[][],int k){
        // basecase 这里的 basecase  有点值得寻味
        // 只需要对 (0, 0) 这个点,做一个 特判 就行了!
        if(i == 0 && j == 0){
            return 0; // 在起点的时候, 一切都是 0
        }
        /*
        这里的代码 明显的不正确!
        并没有 做 i - 1 的一个判断, 所以应该 在 判断 i - 1 >= 0 之后,再进行 这个 递归函数的调用获取上一个 pre 可不可达!
         */
        int ans1 = processUpdate(i - 1,j,colors,money,k), ans2 = processUpdate(i,j - 1,colors,money,k);
        // i - 1, j      // or ans1 != - 1
        if(i - 1 >= 0 && ans1 >= 0){ // 不满足, 说明 无法 从 (i - 1,j) 到达 (i , j)
            if(colors[i - 1][j] == colors[i][j]){
                ans1 += money[i][j];
                // 说明 不相等,需要花费 k 个代价才能通过, 而且按照的题目的要求的话, 好像是 花费  k 之后,还不能欠费,才行
            }else if (ans1 - k >= 0) {
                ans1 += money[i][j] - k;
            }else{
//                ans1 = ans1 - k;  都可以 ,只要设置 成 一个 可以别识别成不可达的一个标志就行 , 但是这里的写法,会决定 最外层的 一个 if条件的判断
                 ans1 = -1;
            }
        }
        if(j - 1 >= 0 && ans2 != -1){
            if(colors[i][j - 1] == colors[i][j]){
                ans2 += money[i][j];
            }
            else if(ans2 - k >= 0){
                ans2 += money[i][j] - k;
            }else{
                ans2 = -1;
            }
        }
        return Math.max(ans1,ans2);
    }

    /*
    记忆化搜索
    一切都联系起来了, 终点 不确定,也是就是最优解 需要 再次 遍历才能找出最优解
    这不是另类的 dp 里面的常见套路嘛
     */

    public int memory(int colors[][],int money[][],int k){
        int n = colors.length;
        int m = colors[0].length;
        // 直接 用Integer
        Integer dp[][] = new Integer[n][m];
        return dp[0][0];
    }
    /*
    直接 dp 就完事 了,
    在dp的过程中,进行一个 最优解的一个 max 计算
     */
    public int dp(int colors[][],int money[][],int k){
        int n = colors.length;
        int m = colors[0].length;
        int dp[][] = new int[n][m];
//        int dp[][] = new int[n][m];
        // 直接设置所有节点,为不可达 的节点,除了 (0, 0) 起点
        Arrays.fill(dp,-1);
        dp[0][0] = 0;
        int ans = 0;
        for(int i = 0;i < n;i++){
            for(int j = 0; j < m;j++){
                // i - 1,j
                if(i - 1 >= 0 && dp[i - 1][j] != -1){
                    if(colors[i - 1][j] == colors[i][j]){
                        dp[i][j] = dp[i - 1][j] + money[i][j];
                    }else if(dp[i - 1][j] - k >= 0){
                        dp[i][j] = dp[i - 1][j] + money[i][j] - k;
                    }
                }
                // i, j - 1
                if(j - 1 >= 0 && dp[i][j - 1] != -1){
                    if(colors[i][j - 1] == colors[i][j]){
                        dp[i][j] = Math.max(dp[i][j],dp[i][j - 1] + money[i][j]);
                    }else if(dp[i][j - 1] - k >= 0){
                        dp[i][j] = Math.max(dp[i][j],dp[i][j - 1] - k + money[i][j]);
                    }
                }
                return Math.max(ans,dp[i][j]);
            }
        }
        return ans;
    }
}
